package com.jxb.test20241216;

import com.jxb.first.ListNode;

public class PalindromeLinkedList_234 {

    public static void main(String[] args) {

    }


    //将链表转成数组,然后用双指针
    public boolean isPalindrome(ListNode head) {
        //将链表转成数组
        int arrLength = 0;
        ListNode temp = head;
        while (temp.next != null) {
            arrLength++;
            temp = temp.next;
        }
        int[] arr = new int[arrLength];
        int index = 0;
        while (head.next != null) {
            arr[index++] = head.val;
            head = head.next;
        }

        //遍历数组
        for (int i = 0,j = arrLength-1;i<arr.length;i++) {
            if (arr[i] != arr[j]) {
                return false;
            }
            j--;
        }
        return true;
    }

    //使用快慢双指针，
    public boolean isPalindrome1(ListNode head) {
        ListNode fp = head;
        ListNode sp = head;
        while (fp != null && fp.next != null) {
            fp = fp.next.next;
            sp = sp.next;
        }

        //反转后半部分链表
        reversp(sp);

        //比较
        while (sp.next != null) {
            if (sp.val != head.val) {
               return false;
            }
            sp = sp.next;
            head = head.next;
        }
        return true;
    }

    private void reversp(ListNode sp) {
        ListNode pre = new ListNode();
        while (sp.next != null) {
            ListNode next = sp.next;
            sp.next = pre;
            pre = sp;
            sp = next;
        }
    }

}
